Lévy Hierarchy

In set theory and mathematical logic, the Lévy hierarchy, introduced by Azriel Lévy in 1965, is a hierarchy of formulas in the formal language of the Zermelo–Fraenkel set theory, which is typically called just the language of set theory. This is analogous to the arithmetical hierarchy, which provides a similar classification for sentences of the language of arithmetic.

Definitions

In the language of set theory, atomic formulas are of the form x = y or x ∈ y, standing for equality and set membership predicates, respectively.

The first level of the Lévy hierarchy is defined as containing only formulas with no unbounded quantifiers, and is denoted by $\Delta _0=\Sigma_0=\Pi_0$.Walicki, Michal (2012). ''Mathematical Logic'', p. 225. World Scientific Publishing Co. Pte. Ltd. The next levels are given by finding an equivalent formula in prenex normal form, and counting the number of changes of quantifiers:

In the theory ZFC, a formula $A$ is called:

$\Sigma _$ if $A$ is equivalent to $\exists x _1 ... \exists x _n B$ in ZFC, where $B$ is $\Pi _i$

$\Pi _$ if $A$ is equivalent to $\forall x _1 ... \forall x _n B$ in ZFC, where $B$ is $\Sigma _i$

If a formula is both $\Sigma _i$ and $\Pi _i$, it is called $\Delta _i$. As a formula might have several different equivalent formulas in prenex normal form, it might belong to several different levels of the hierarchy. In this case, the lowest possible level is the level of the formula.

Alternatively, Lévy also used $\Sigma_i^\mathsf$ (resp. $\Pi_i^\mathsf$) for formulae that are provably logically equivalent to one of those in $\Sigma_i$ (resp. $\Pi_i$), and Pohlers has defined $\Delta_1$ in particular semantically, in which a formula is "$\Delta_1$ in a structure $M$".

The Lévy hierarchy is sometimes defined for other theories ''S''. In this case $\Sigma_i$ and $\Pi _i$ by themselves refer only to formulas that start with a sequence of quantifiers with at most ''i''−1 alternations, and $\Sigma_i^S$ and $\Pi_i^S$ refer to formulas equivalent to $\Sigma_i$ and $\Pi_i$ formulas in the language of the theory ''S''. So strictly speaking the levels $\Sigma_i$ and $\Pi _i$ of the Lévy hierarchy for ZFC defined above should be denoted by $\Sigma^ _i$ and $\Pi^ _i$.

Examples

Σ₀=Π₀=Δ₀ formulas and concepts

*x =
*x ⊆ y.
*''x'' is a transitive set.
*''x'' is an ordinal, ''x'' is a limit ordinal, ''x'' is a successor ordinalD. Monk 2011
Graduate Set Theory
(pp.168--170). Archived 2011-12-06
*''x'' is a finite ordinal
*The first countable ordinal ω.
*''f'' is a function. ''x'' is the range or domain of the function ''f''. ''y'' is the value of ''f'' on ''x''.
*The Cartesian product of two sets.
*''x'' is the union of ''y''.
*''x'' is a member of the ''α''th level of Godel's L.

Δ₁-formulas and concepts

* ''x'' is a well-founded relation on ''y''.
* ''x'' is finite
*Ordinal addition and multiplication and exponentiation
*The rank (with respect to Gödel's constructible universe) of a setJon Barwise, ''Admissible Sets and Structures'' (1975) (p.61)
*The transitive closure of a set

Σ₁-formulas and concepts

* ''x'' is countable
*, ''X'', ≤, ''Y'', , , ''X'', =, ''Y'',
*''x'' is constructible

Π₁-formulas and concepts

* ''x'' is a cardinal
* ''x'' is a regular cardinal
* ''x'' is a limit cardinal
* ''x'' is an inaccessible cardinal.
* ''x'' is the powerset of ''y''

Δ₂-formulas and concepts

*''κ'' is ''γ''- supercompact

Σ₂-formulas and concepts

* the continuum hypothesis
* there exists an inaccessible cardinal
* there exists a measurable cardinal
* ''κ'' is an ''n''-huge cardinal

Π₂-formulas and concepts

* The axiom of constructibility: '' V'' = '' L''

Δ₃-formulas and concepts

Σ₃-formulas and concepts

* there exists a supercompact cardinal

Π₃-formulas and concepts

* ''κ'' is an extendible cardinal

Σ₄-formulas and concepts

* there exists an extendible cardinal

Properties

Jech p. 184
Devlin p. 29

See also

* Arithmetic hierarchy
* Absoluteness

References

*
*
*
*

{{DEFAULTSORT:Levy hierarchy
Mathematical logic
Set theory
Mathematical logic hierarchies